package mine.code.practice;

import org.junit.Test;

import java.util.Arrays;

/**
 * 马拉车算法
 *
 * @author caijinnan
 * @date 2020/3/27 11:28
 */
public class Manacher {
    @Test
    public void run2() {
//        String str = "#a#b#c#c#b#a#";
        String str = "bab";
        char[] charArr = str.toCharArray();
        int strLength = str.length();
        //以center中心的回文字符串最远边界
        int maxRight = 0;
        //回文中心
        int center = 0;
        //每一个位置对应的回文半径
        int[] radiusLength = new int[strLength];
        for (int i = 0; i < strLength; i++) {
            radiusLength[i] = i >= maxRight ? 1 : Math.min(radiusLength[2 * center - i], maxRight - i);
            //统计以i为中心点,最长回文边界
            while (true) {
                int left = i - radiusLength[i];
                int right = i + radiusLength[i];
                if (left < 0 || right > strLength - 1 || charArr[right] != charArr[left]) {
                    break;
                }
                radiusLength[i]++;
            }
            //更换中心点和最远边界
            if (maxRight < i + radiusLength[i]) {
                maxRight = i + radiusLength[i];
                center = i;
            }
        }
        System.out.println(Arrays.toString(radiusLength));
    }
    // c    0
    // mr   0
    // i    0  1  2  3  4  5  6  7  8  9  10 11 12
    //      #  a  #  b  #  c  #  c  #  b  #  a  #
    //p[i]  1  2  1  2  1  2  7  2  1  2  1  2  1
}
